package srcInterviewPrep;

public class MaxContinousSubArray 
{
    public static void Kadanes(int[] nums)
    {
        int maxSum = 0;
        int maxSumEnd = -1;
        int maxElemsCount = 0;
        
        int localSum = 0;
        int localElemsCount = 0;
        
        for (int i = 0; i < nums.length; ++i)
        {
            localSum += nums[i];
            ++localElemsCount;
            
            if (localSum > maxSum)
            {
                maxSum = localSum;
                maxSumEnd = i;
                maxElemsCount = localElemsCount;
                continue;
            }
            
            if (localSum <= 0)
            {
                localSum = 0;
                localElemsCount = 0;
            }
        }
        
        System.out.println("Max Sum" + maxSum);
        
        for (int i = 0; i < maxElemsCount; ++i)
        {
            System.out.print(nums[maxSumEnd - maxElemsCount + 1 + i]);
            System.out.print(' ');
        }
        
    }
    
    public static void DPBasedSolution(int[] nums)
    {
        int prev = 0;
        int max = 0;
        
        for (int i = 1; i <= nums.length; ++i)
        {
            prev = Math.max(prev + nums[i-1], 0);
            if (prev > max)
            {
                max = prev;
            }
        }
        
        System.out.println("Max: " + max);
    }

}
